package top100.dynamic;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/22 9:59
 * @description: 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 * 示例 2：
 * <p>
 * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
 * 输出：5
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 100
 */
public class Solution718 {
    public int findLength(int[] nums1, int[] nums2) {
        //dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度
        //这个定义决定了初始化的含义
        int[][] dp = new int[nums1.length][nums2.length];
        int maxLen = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (nums2[0] == nums1[i]) {
                dp[i][0] = 1;
                maxLen = 1;
            }
        }
        for (int i = 0; i < nums2.length; i++) {
            if (nums1[0] == nums2[i]) {
                dp[0][i] = 1;
                maxLen = 1;
            }
        }
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
//        for (int i = 0; i < nums1.length; i++) {
//            for (int j = 0; j < nums2.length; j++) {
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//
//        }
        return maxLen;
    }

    public static void main(String[] args) {
        Solution718 s = new Solution718();
        System.out.println(s.findLength(new int[]{1, 0, 0, 0, 1}, new int[]{1, 0, 0, 1, 1}));
    }
}
